# Pow(x, n): https://leetcode-cn.com/problems/powx-n/

# 空间时间复杂度都会 O(logn), 递归会使用系统的递归栈
class Solution:
    def myPow(self, x: float, n: int) -> float:
        """
            递归求解，快速幂 根据奇偶性，得到正确的幂。 下面表示 x^幂
            1 2 4 8 16 32 64
            1 2 4 9 19 38 77  注意看这个，为奇数时需要额外乘 x
        """
        def QucketPow(n: int):
            if n == 0: return 1.0
            # 其实这个 == 
            if n == 1: return x
            
            y = QucketPow(n // 2)

            return y*y if n % 2 == 0 else y*y*x

        return QucketPow(n) if n > 0 else 1 / QucketPow(-n)



# 配合位运算的迭代 快速幂，while循环
class Solution:
    def myPow(self, x: float, n: int) -> float:
        """
            递归求解的问题都可以化为 while循环，非递归求解。 分步迭代
        """
        if n < 0: x = 1/x; n = -n

        rst = 1.0
        while n != 0:
            if n & 1 == 1: rst *= x
            x *= x
            n >>= 1

        return rst


